package tree;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;

// 思路1: BFS like TreeNode.buildTree(), 压缩了null节点
// 思路2: 前序遍历: 注意null节点要单独
// 思路3: 后序遍历: 注意反序列化时要从后往前
// 注意: 中序遍历无法反序列化
public class SerializeAndDeserializeBinaryTree297 {

    @Test
    public void test() {
        print(Arrays.asList(1,2,3,null,null,4,5));
    }

    void print(List<Integer> list) {
        TreeNode root = TreeNode.buildTree(list);
        String s = serialize(root);
        TreeNode root2 = deserialize(s);
        System.out.format("tree: %s, string: %s\n", list, s);
    }

    final String SEP = ",";
    final String NULL = "#";
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        serialize(root, sb);
        return sb.toString();
    }

    public void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append(NULL);
            sb.append(SEP);
            return;
        }
        sb.append(node.val);
        sb.append(SEP);
        serialize(node.left, sb);
        //sb.append(SEP); // 不需要这个了, 每个实际的val之后, 都有一个SEP了
        serialize(node.right, sb);
        //sb.append(SEP);
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) {
            return null;
        }
        String[] s = data.split(SEP);
        return deserialize(s, new IndexWrapper(0));
    }

    public TreeNode deserialize(String[] s, IndexWrapper index) {
        if (index.value >= s.length) {
            return null;
        }

        if (NULL.equals(s[index.value])) {
            index.value++;
            return null;
        }
        int val = Integer.parseInt(s[index.value]);
        TreeNode node = new TreeNode(val);
        index.value++;
        node.left = deserialize(s, index);
        node.right = deserialize(s, index);
        return node;
    }

    static class IndexWrapper {
        int value;
        IndexWrapper(int value) {
            this.value = value;
        }
    }
}
